package trb.complexshield.bool;

import java.util.ArrayList;
import java.util.List;

/**
 * A sorted list of segments that do not overlap.
 */
public class Segments {
    private static final int INITIAL_LENGTH = 16;
    public float[] data = new float[INITIAL_LENGTH];
    public int segmentCount = 0;

    void ensureCapacity(int minSize) {
        if (data.length < minSize) {
            int newSize = Math.max(data.length * 2, minSize);
            float[] newData = new float[newSize];
            System.arraycopy(data, 0, newData, 0, data.length);
            data = newData;
        }
    }

    public void clear() {
        segmentCount = 0;
    }

    public float from(int idx) {
        return data[idx*2];
    }

    public float to(int idx) {
        return data[idx*2+1];
    }

    public void addAtEnd(float from, float to) {
        ensureCapacity(segmentCount * 2 + 2);
        data[segmentCount*2] = from;
        data[segmentCount*2+1] = to;
        segmentCount++;

    }

    private void setTo(int idx, float to) {
        if (idx >= segmentCount) {
            throw new IndexOutOfBoundsException();
        }

        data[idx*2+1] = to;
    }

    private void setFrom(int idx, float from) {
        if (idx >= segmentCount) {
            throw new IndexOutOfBoundsException();
        }

        data[idx*2] = from;
    }

    public static Segments create(float... floats) {
        if ((floats.length % 1) != 0) {
            throw new IllegalArgumentException("Not even number of floats: " + floats.length);
        }
        Segments segments = new Segments();
        segments.ensureCapacity(floats.length);
        System.arraycopy(floats, 0, segments.data, 0, floats.length);
        segments.segmentCount = floats.length >> 1;
        return segments;
    }

    /**
     * out = a - b
     */
    public static Segments subtract(Segments a, Segments b, Segments out) {
        out.segmentCount = 0;
        int aIdx = 0;
        int bIdx = 0;

        while (aIdx < a.segmentCount && bIdx < b.segmentCount) {
            if (b.to(bIdx) < a.from(aIdx)) {
                // b is before a
                bIdx++;
                continue;
            }
            if (b.from(bIdx) > a.to(aIdx)) {
                // b is after a
                out.addAtEnd(a.from(aIdx), a.to(aIdx));
                aIdx++;
                continue;
            }

            out.addAtEnd(a.from(aIdx), a.to(aIdx));
            aIdx++;

            // while b is inside last in out
            while (bIdx < b.segmentCount && b.from(bIdx) < out.to(out.segmentCount-1)) {
                if (b.from(bIdx) < out.from(out.segmentCount-1)) {
                    // b starts before out
                    if (b.to(bIdx) > out.to(out.segmentCount-1)) {
                        // .. and ends after out: remove out
                        out.segmentCount--;
                        break;
                    }
                    // .. and ends before out
                    out.setFrom(out.segmentCount-1, b.to(bIdx));
                    bIdx++;
                } else {
                    // b starts after out
                    if (b.to(bIdx) > out.to(out.segmentCount-1)) {
                        // .. and ends after out
                        out.setTo(out.segmentCount-1, b.from(bIdx));
                        break;
                    } else {
                        // ..and ends before out (inside out)
                        float outTo = out.to(out.segmentCount-1);
                        out.setTo(out.segmentCount-1, b.from(bIdx));
                        out.addAtEnd(b.to(bIdx), outTo);
                        bIdx++;
                    }
                }
            }
        }

        while (aIdx < a.segmentCount) {
            out.addAtEnd(a.from(aIdx), a.to(aIdx));
            aIdx++;
        }

        return out;
    }

    public static Segments merge(Segments a, Segments b, Segments out) {
        out.segmentCount = 0;
        int aIdx = 0;
        int bIdx = 0;
        while (aIdx < a.segmentCount || bIdx < b.segmentCount) {
            Segments minSeg = null;
            int minIdx = 0;
            if (bIdx >= b.segmentCount || (aIdx < a.segmentCount && a.from(aIdx) < b.from(bIdx))) {
                minSeg = a;
                minIdx = aIdx;
                aIdx++;
            } else {
                minSeg = b;
                minIdx = bIdx;
                bIdx++;
            }

            if (out.segmentCount <= 0) {
                out.addAtEnd(minSeg.data[minIdx*2], minSeg.data[minIdx*2+1]);
            } else {
                if (minSeg.from(minIdx) > out.to(out.segmentCount-1)) {
                    // after end of out
                    out.addAtEnd(minSeg.from(minIdx), minSeg.to(minIdx));
                } else {
                    // overlap
                    if (minSeg.to(minIdx) > out.to(out.segmentCount-1)) {
                        // new segment is higher than current
                        out.setTo(out.segmentCount-1, minSeg.to(minIdx));
                    }
                }
            }
        }

        return out;
    }


    public static Segments merge(Segments[] segmentsList, Segments out) {
        out.segmentCount = 0;
        int[] indexes = new int[segmentsList.length];
        while (true) {
            Segments minSeg = null;
            int segmentIndex = -1;
            int minIdx = -1;
            float minFrom = Float.NaN;
            for (int i=0; i<indexes.length; i++) {
                Segments s = segmentsList[i];
                int index = indexes[i];
                if (index < s.segmentCount) {
                    if (Float.isNaN(minFrom) || s.from(index) < minFrom) {
                        minSeg = s;
                        minIdx = index;
                        minFrom = s.from(minIdx);
                        segmentIndex = i;
                    }
                }
            }
            if (minIdx == -1) {
                break;
            }
            indexes[segmentIndex]++;

            if (out.segmentCount <= 0) {
                out.addAtEnd(minSeg.from(minIdx), minSeg.to(minIdx));
            } else {
                if (minSeg.from(minIdx) > out.to(out.segmentCount-1)) {
                    // after end of out
                    out.addAtEnd(minSeg.from(minIdx), minSeg.to(minIdx));
                } else {
                    // overlap
                    if (minSeg.to(minIdx) > out.to(out.segmentCount-1)) {
                        // new segment is higher than current
                        out.setTo(out.segmentCount-1, minSeg.to(minIdx));
                    }
                }
            }
        }

        return out;
    }

    public static List<Segments> toList(Segments... segmentsArray) {
        List<Segments> list = new ArrayList(segmentsArray.length);
        for (Segments segments : segmentsArray) {
            list.add(segments);
        }
        return list;
    }
}
